package ljl.alg.wangzheng_camp.round1.backtrack;

import java.util.ArrayList;
import java.util.List;

public class _22_gen_par {
    
    /**
     * left 和 right，left 任何时候不得小于 right，往里 append 就行了
     */
    List<String> res = new ArrayList<>();
    
    public List<String> generateParenthesis(int n) {
        backtrack(new StringBuilder(), n, n);
        return res;
    }
    
    void backtrack(StringBuilder sb, int left, int right) {
        if (left == 0 && right == 0) res.add(sb.toString());
        else {
            if (left == right) {
                sb.append("(");
                backtrack(sb, left - 1, right);
                sb.deleteCharAt(sb.length() - 1);
            } else if (left < right) {
                sb.append(")");
                backtrack(sb, left, right - 1);
                sb.deleteCharAt(sb.length() - 1);
                if (left > 0) {
                    sb.append("(");
                    backtrack(sb, left - 1, right);
                    sb.deleteCharAt(sb.length() - 1);
                }
            }
        }
    }
    
    /**
     * 暴力法，居然不慢
     * 直接生成所有情况，判断是否合理
     */
    static class force {
        
        public List<String> generateParenthesis(int n) {
            List<String> res = new ArrayList<>();
            gen(new char[2 * n], 0, res);
            return res;
        }
        
        public void gen(char[] cur, int pos, List<String> res) {
            if (pos == cur.length) {
                if (good(cur)) res.add(new String(cur));
            } else {
                cur[pos] = '(';
                gen(cur, pos + 1, res);
                cur[pos] = ')';
                gen(cur, pos + 1, res);
            }
        }
        
        boolean good(char[] arr) {
            int l = 0, r = 0;
            for (char c : arr) {
                if (c == '(') l++;
                else r++;
                if (r > l) return false;
            }
            return l == r;
        }
    }
    
    /**
     * 我的任务就是把官方题解改的难以看懂
     */
    static class track1 {
        
        List<String> res = new ArrayList<>();
        int n;
        StringBuilder buf = new StringBuilder();
        
        public List<String> generateParenthesis(int n) {
            this.n = n;
            b(0, 0);
            return res;
        }
        
        void b(int o, int c) {
            if (buf.length() == n * 2) res.add(buf.toString());
            else {
                if (o < n) wrap('(', () -> b(o + 1, c));
                if (c < o) wrap(')', () -> b(o, c + 1));
            }
        }
        
        void wrap(char c, Runnable r) {
            buf.append(c);
            r.run();
            buf.deleteCharAt(buf.length() - 1);
        }
    }
    
    /**
     * 很聪明，啊很聪明
     * 任何一个括号，都是 ( 开始的对吧，然后肯定有个结束符号；可以得出所有括号都是 ( a ) b 格式的
     * 枚举所有 a 和 b，用一个函数 generate(i) 生成完 a 之后，b 所有情况就是 generate(n - 1 - i)
     * 然后组合所有的 a 和 b
     *
     * 这个不好想的
     * */
    static class track2 {
        @SuppressWarnings("unchecked")
        List<String>[] cache = new ArrayList[100];
        
        public List<String> generate(int n) {
            if (cache[n] != null) {
                return cache[n];
            }
            ArrayList<String> ans = new ArrayList<>();
            if (n == 0) {
                ans.add("");
            } else {
                for (int c = 0; c < n; ++c) {
                    for (String left : generate(c)) {
                        for (String right : generate(n - 1 - c)) {
                            ans.add("(" + left + ")" + right);
                        }
                    }
                }
            }
            cache[n] = ans;
            return ans;
        }
        
        public List<String> generateParenthesis(int n) {
            return generate(n);
        }
    }
}
